/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / Implement.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 0a 7b 5c 6d 61 67 74 77 | 6f 20 39 2e 20 49 6d 70 |.{\magtw|o 9. Imp|
|00000010| 6c 65 6d 65 6e 74 61 74 | 69 6f 6e 73 7d 0a 0a 7b |lementat|ions}..{|
|00000020| 5c 6d 61 67 6f 6e 65 62 | 66 20 39 2e 31 20 4c 69 |\magoneb|f 9.1 Li|
|00000030| 73 74 20 6f 66 20 64 61 | 74 61 20 73 74 72 75 63 |st of da|ta struc|
|00000040| 74 75 72 65 73 7d 0a 0a | 54 68 69 73 20 73 65 63 |tures}..|This sec|
|00000050| 74 69 6f 6e 20 6c 69 73 | 74 73 20 74 68 65 20 64 |tion lis|ts the d|
|00000060| 61 74 61 20 73 74 72 75 | 63 74 75 72 65 73 20 66 |ata stru|ctures f|
|00000070| 6f 72 20 64 69 63 74 69 | 6f 6e 61 72 69 65 73 2c |or dicti|onaries,|
|00000080| 20 64 69 63 74 69 6f 6e | 61 72 79 0a 61 72 72 61 | diction|ary.arra|
|00000090| 79 73 2c 20 70 72 69 6f | 72 69 74 79 20 71 75 65 |ys, prio|rity que|
|000000a0| 75 65 73 2c 20 61 6e 64 | 20 67 65 6f 6d 65 74 72 |ues, and| geometr|
|000000b0| 69 63 20 64 61 74 61 20 | 74 79 70 65 73 20 63 75 |ic data |types cu|
|000000c0| 72 72 65 6e 74 6c 79 20 | 63 6f 6e 74 61 69 6e 65 |rrently |containe|
|000000d0| 64 20 69 6e 20 4c 45 44 | 41 2e 20 0a 46 6f 72 20 |d in LED|A. .For |
|000000e0| 65 61 63 68 20 6f 66 20 | 74 68 65 20 64 61 74 61 |each of |the data|
|000000f0| 20 73 74 72 75 63 74 75 | 72 65 73 20 69 74 73 20 | structu|res its |
|00000100| 6e 61 6d 65 20 61 6e 64 | 20 74 79 70 65 2c 20 74 |name and| type, t|
|00000110| 68 65 20 6c 69 73 74 20 | 6f 66 20 4c 45 44 41 20 |he list |of LEDA |
|00000120| 64 61 74 61 20 74 79 70 | 65 73 20 0a 69 74 20 63 |data typ|es .it c|
|00000130| 61 6e 20 69 6d 70 6c 65 | 6d 65 6e 74 2c 20 61 6e |an imple|ment, an|
|00000140| 64 20 61 20 6c 69 74 65 | 72 61 74 75 72 65 20 72 |d a lite|rature r|
|00000150| 65 66 65 72 65 6e 63 65 | 20 61 72 65 20 67 69 76 |eference| are giv|
|00000160| 65 6e 2e 0a 42 65 66 6f | 72 65 20 75 73 69 6e 67 |en..Befo|re using|
|00000170| 20 61 20 64 61 74 61 20 | 73 74 72 75 63 74 75 72 | a data |structur|
|00000180| 65 73 20 24 78 79 7a 24 | 20 74 68 65 20 63 6f 72 |es $xyz$| the cor|
|00000190| 72 65 73 70 6f 6e 64 69 | 6e 67 20 68 65 61 64 65 |respondi|ng heade|
|000001a0| 72 20 66 69 6c 65 0a 5c | 3c 4c 45 44 41 2f 69 6d |r file.\|<LEDA/im|
|000001b0| 70 6c 2f 24 78 79 7a 24 | 2e 68 5c 3e 20 68 61 73 |pl/$xyz$|.h\> has|
|000001c0| 20 74 6f 20 62 65 20 69 | 6e 63 6c 75 64 65 64 20 | to be i|ncluded |
|000001d0| 28 63 66 2e 7e 73 65 63 | 74 69 6f 6e 7e 31 2e 32 |(cf.~sec|tion~1.2|
|000001e0| 20 66 6f 72 20 61 6e 20 | 65 78 61 6d 70 6c 65 29 | for an |example)|
|000001f0| 2e 0a 0a 7b 5c 62 66 20 | 39 2e 31 2e 31 20 44 69 |...{\bf |9.1.1 Di|
|00000200| 63 74 69 6f 6e 61 72 69 | 65 73 7d 0a 5c 2b 5c 63 |ctionari|es}.\+\c|
|00000210| 6c 65 61 72 74 61 62 73 | 20 5c 68 73 6b 69 70 20 |leartabs| \hskip |
|00000220| 32 2e 37 74 72 75 65 63 | 6d 20 26 20 5c 68 73 6b |2.7truec|m & \hsk|
|00000230| 69 70 20 34 2e 35 74 72 | 75 65 63 6d 20 26 20 5c |ip 4.5tr|uecm & \|
|00000240| 68 73 6b 69 70 20 36 74 | 72 75 65 63 6d 20 26 5c |hskip 6t|ruecm &\|
|00000250| 63 72 0a 5c 2b 24 61 62 | 5c 5f 74 72 65 65 24 20 |cr.\+$ab|\_tree$ |
|00000260| 20 20 20 26 61 2d 62 20 | 74 72 65 65 20 20 20 20 |   &a-b |tree    |
|00000270| 20 20 20 20 20 20 20 26 | 64 69 63 74 69 6f 6e 61 |       &|dictiona|
|00000280| 72 79 2c 20 64 5c 5f 61 | 72 72 61 79 2c 20 7b 5c |ry, d\_a|rray, {\|
|00000290| 62 66 20 73 6f 72 74 73 | 65 71 7d 26 5b 42 43 37 |bf sorts|eq}&[BC7|
|000002a0| 32 5d 5c 63 72 0a 5c 2b | 24 61 76 6c 5c 5f 74 72 |2]\cr.\+|$avl\_tr|
|000002b0| 65 65 24 20 20 20 26 41 | 56 4c 20 74 72 65 65 20 |ee$   &A|VL tree |
|000002c0| 20 20 20 20 20 20 20 20 | 20 20 26 64 69 63 74 69 |        |  &dicti|
|000002d0| 6f 6e 61 72 79 2c 20 64 | 5c 5f 61 72 72 61 79 20 |onary, d|\_array |
|000002e0| 20 20 20 20 20 20 20 20 | 20 26 5b 41 56 4c 36 32 |        | &[AVL62|
|000002f0| 5d 5c 63 72 0a 5c 2b 24 | 62 62 5c 5f 74 72 65 65 |]\cr.\+$|bb\_tree|
|00000300| 24 20 20 20 20 26 42 42 | 5b 24 5c 61 6c 70 68 61 |$    &BB|[$\alpha|
|00000310| 24 5d 20 74 72 65 65 20 | 20 26 64 69 63 74 69 6f |$] tree | &dictio|
|00000320| 6e 61 72 79 2c 20 64 5c | 5f 61 72 72 61 79 2c 20 |nary, d\|_array, |
|00000330| 73 6f 72 74 73 65 71 20 | 26 5b 42 4d 38 30 5d 20 |sortseq |&[BM80] |
|00000340| 5c 63 72 0a 5c 2b 24 63 | 68 5c 5f 68 61 73 68 69 |\cr.\+$c|h\_hashi|
|00000350| 6e 67 24 20 26 68 61 73 | 68 69 6e 67 20 77 69 74 |ng$ &has|hing wit|
|00000360| 68 20 63 68 61 69 6e 69 | 6e 67 20 26 64 69 63 74 |h chaini|ng &dict|
|00000370| 69 6f 6e 61 72 79 2c 20 | 64 5c 5f 61 72 72 61 79 |ionary, |d\_array|
|00000380| 20 20 20 20 20 20 20 26 | 5b 4d 38 34 5d 5c 63 72 |       &|[M84]\cr|
|00000390| 0a 5c 2b 24 64 70 5c 5f | 68 61 73 68 69 6e 67 24 |.\+$dp\_|hashing$|
|000003a0| 20 26 64 79 6e 2e 20 70 | 65 72 66 2e 20 68 61 73 | &dyn. p|erf. has|
|000003b0| 68 69 6e 67 20 26 7b 5c | 62 66 20 68 5c 5f 61 72 |hing &{\|bf h\_ar|
|000003c0| 72 61 79 7d 20 20 20 20 | 20 20 20 20 20 20 20 26 |ray}    |       &|
|000003d0| 5b 44 4b 4d 4d 52 54 38 | 38 2c 57 39 32 5d 5c 63 |[DKMMRT8|8,W92]\c|
|000003e0| 72 0a 5c 2b 24 70 65 72 | 73 5c 5f 74 72 65 65 24 |r.\+$per|s\_tree$|
|000003f0| 20 20 26 70 65 72 73 69 | 73 74 65 6e 74 20 20 20 |  &persi|stent   |
|00000400| 74 72 65 65 20 20 26 7b | 5c 62 66 20 70 5c 5f 64 |tree  &{|\bf p\_d|
|00000410| 69 63 74 69 6f 6e 61 72 | 79 7d 20 20 20 20 20 20 |ictionar|y}      |
|00000420| 26 5b 44 53 53 54 38 39 | 5d 5c 63 72 0a 5c 2b 24 |&[DSST89|]\cr.\+$|
|00000430| 72 62 5c 5f 74 72 65 65 | 24 20 20 20 20 26 72 65 |rb\_tree|$    &re|
|00000440| 64 2d 62 6c 61 63 6b 20 | 74 72 65 65 20 20 20 20 |d-black |tree    |
|00000450| 20 26 64 69 63 74 69 6f | 6e 61 72 79 2c 20 64 5c | &dictio|nary, d\|
|00000460| 5f 61 72 72 61 79 2c 20 | 73 6f 72 74 73 65 71 20 |_array, |sortseq |
|00000470| 26 5b 47 53 37 38 5d 20 | 5c 63 72 0a 5c 2b 24 72 |&[GS78] |\cr.\+$r|
|00000480| 73 5c 5f 74 72 65 65 24 | 20 20 20 20 26 72 61 6e |s\_tree$|    &ran|
|00000490| 64 2e 20 73 65 61 72 63 | 68 20 74 72 65 65 20 20 |d. searc|h tree  |
|000004a0| 26 7b 5c 62 66 20 64 69 | 63 74 69 6f 6e 61 72 79 |&{\bf di|ctionary|
|000004b0| 7d 2c 20 7b 5c 62 66 20 | 64 5c 5f 61 72 72 61 79 |}, {\bf |d\_array|
|000004c0| 7d 2c 20 73 6f 72 74 73 | 65 71 20 26 5b 41 53 38 |}, sorts|eq &[AS8|
|000004d0| 39 5d 5c 63 72 0a 5c 2b | 24 73 6b 69 70 6c 69 73 |9]\cr.\+|$skiplis|
|000004e0| 74 24 20 20 20 20 26 73 | 6b 69 70 20 6c 69 73 74 |t$    &s|kip list|
|000004f0| 73 20 20 20 20 20 20 20 | 20 20 26 64 69 63 74 69 |s       |  &dicti|
|00000500| 6f 6e 61 72 79 2c 20 64 | 5c 5f 61 72 72 61 79 2c |onary, d|\_array,|
|00000510| 20 73 6f 72 74 73 65 71 | 20 20 26 5b 50 75 39 30 | sortseq|  &[Pu90|
|00000520| 5d 5c 63 72 0a 0a 0a 7b | 5c 62 66 20 39 2e 31 2e |]\cr...{|\bf 9.1.|
|00000530| 32 20 50 72 69 6f 72 69 | 74 79 20 51 75 65 75 65 |2 Priori|ty Queue|
|00000540| 73 7d 0a 5c 6d 65 64 73 | 6b 69 70 0a 5c 2b 24 66 |s}.\meds|kip.\+$f|
|00000550| 5c 5f 68 65 61 70 24 20 | 20 20 20 26 46 69 62 6f |\_heap$ |   &Fibo|
|00000560| 6e 6e 61 63 63 69 20 68 | 65 61 70 20 20 20 26 7b |nnacci h|eap   &{|
|00000570| 5c 62 66 20 70 72 69 6f | 72 69 74 79 5c 5f 71 75 |\bf prio|rity\_qu|
|00000580| 65 75 65 7d 20 26 5b 46 | 54 38 37 5d 5c 63 72 0a |eue} &[F|T87]\cr.|
|00000590| 5c 2b 24 70 5c 5f 68 65 | 61 70 24 20 20 20 20 26 |\+$p\_he|ap$    &|
|000005a0| 70 61 69 72 69 6e 67 20 | 68 65 61 70 20 20 20 20 |pairing |heap    |
|000005b0| 20 20 26 70 72 69 6f 72 | 69 74 79 5c 5f 71 75 65 |  &prior|ity\_que|
|000005c0| 75 65 20 20 20 20 20 20 | 20 26 5b 53 56 38 37 5d |ue      | &[SV87]|
|000005d0| 5c 63 72 0a 5c 2b 24 6b | 5c 5f 68 65 61 70 24 20 |\cr.\+$k|\_heap$ |
|000005e0| 20 20 20 26 6b 2d 6e 61 | 72 79 20 68 65 61 70 20 |   &k-na|ry heap |
|000005f0| 20 20 20 20 20 20 26 70 | 72 69 6f 72 69 74 79 5c |      &p|riority\|
|00000600| 5f 71 75 65 75 65 20 20 | 20 20 20 20 20 26 5b 4d |_queue  |     &[M|
|00000610| 38 34 5d 5c 63 72 0a 5c | 2b 24 6d 5c 5f 68 65 61 |84]\cr.\|+$m\_hea|
|00000620| 70 24 20 20 20 20 26 6d | 6f 6e 6f 74 6f 6e 69 63 |p$    &m|onotonic|
|00000630| 20 68 65 61 70 20 20 20 | 20 26 70 72 69 6f 72 69 | heap   | &priori|
|00000640| 74 79 5c 5f 71 75 65 75 | 65 20 20 20 20 20 20 20 |ty\_queu|e       |
|00000650| 26 5b 4d 38 34 5d 5c 63 | 72 0a 5c 2b 24 65 62 5c |&[M84]\c|r.\+$eb\|
|00000660| 5f 74 72 65 65 24 20 20 | 20 26 45 6d 64 65 2d 42 |_tree$  | &Emde-B|
|00000670| 6f 61 73 20 74 72 65 65 | 20 20 20 20 26 70 72 69 |oas tree|    &pri|
|00000680| 6f 72 69 74 79 5c 5f 71 | 75 65 75 65 20 20 20 20 |ority\_q|ueue    |
|00000690| 20 20 20 26 5b 45 4b 5a | 37 37 2c 57 39 32 5d 5c |   &[EKZ|77,W92]\|
|000006a0| 63 72 0a 0a 7b 5c 62 66 | 20 39 2e 31 2e 33 20 47 |cr..{\bf| 9.1.3 G|
|000006b0| 65 6f 6d 65 74 72 79 7d | 0a 5c 6d 65 64 73 6b 69 |eometry}|.\medski|
|000006c0| 70 0a 5c 2b 24 72 61 6e | 67 65 5c 5f 74 72 65 65 |p.\+$ran|ge\_tree|
|000006d0| 24 20 26 72 61 6e 67 65 | 20 74 72 65 65 20 20 20 |$ &range| tree   |
|000006e0| 20 20 26 7b 5c 62 66 20 | 64 32 5c 5f 64 69 63 74 |  &{\bf |d2\_dict|
|000006f0| 69 6f 6e 61 72 79 7d 2c | 20 7b 5c 62 66 20 70 6f |ionary},| {\bf po|
|00000700| 69 6e 74 5c 5f 73 65 74 | 7d 26 5b 57 69 38 35 2c |int\_set|}&[Wi85,|
|00000710| 4c 75 37 38 5d 5c 63 72 | 0a 5c 2b 24 73 65 67 5c |Lu78]\cr|.\+$seg\|
|00000720| 5f 74 72 65 65 24 20 20 | 20 26 73 65 67 6d 65 6e |_tree$  | &segmen|
|00000730| 74 20 74 72 65 65 20 20 | 20 20 20 20 20 20 20 26 |t tree  |       &|
|00000740| 7b 5c 62 66 20 73 65 67 | 5c 5f 73 65 74 7d 20 20 |{\bf seg|\_set}  |
|00000750| 20 20 20 20 26 5b 42 37 | 39 2c 45 64 38 32 5d 5c |    &[B7|9,Ed82]\|
|00000760| 63 72 0a 5c 2b 24 70 73 | 5c 5f 74 72 65 65 24 20 |cr.\+$ps|\_tree$ |
|00000770| 20 20 20 26 70 72 69 6f | 72 69 74 79 20 73 65 61 |   &prio|rity sea|
|00000780| 72 63 68 20 74 72 65 65 | 20 26 5c 20 5c 20 2d 2d |rch tree| &\ \ --|
|00000790| 2d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 26 5b |-       |      &[|
|000007a0| 4d 43 38 31 5d 5c 63 72 | 0a 5c 2b 24 69 76 5c 5f |MC81]\cr|.\+$iv\_|
|000007b0| 74 72 65 65 24 20 20 20 | 20 26 69 6e 74 65 72 76 |tree$   | &interv|
|000007c0| 61 6c 20 74 72 65 65 20 | 20 20 20 20 20 20 20 26 |al tree |       &|
|000007d0| 7b 5c 62 66 20 69 6e 74 | 65 72 76 61 6c 5c 5f 73 |{\bf int|erval\_s|
|000007e0| 65 74 7d 20 26 5b 4d 43 | 38 30 2c 45 64 38 32 5d |et} &[MC|80,Ed82]|
|000007f0| 5c 63 72 0a 5c 2b 24 64 | 65 6c 61 75 6e 61 79 5c |\cr.\+$d|elaunay\|
|00000800| 5f 74 72 65 65 24 20 26 | 64 65 6c 61 75 6e 61 79 |_tree$ &|delaunay|
|00000810| 20 74 72 65 65 20 20 20 | 20 20 26 7b 5c 62 66 20 | tree   |  &{\bf |
|00000820| 70 6f 69 6e 74 5c 5f 73 | 65 74 7d 20 20 20 20 26 |point\_s|et}    &|
|00000830| 5b 44 65 39 32 5d 5c 63 | 72 0a 0a 5c 76 66 69 6c |[De92]\c|r..\vfil|
|00000840| 6c 5c 65 6a 65 63 74 0a | 0a 5c 62 69 67 73 6b 69 |l\eject.|.\bigski|
|00000850| 70 0a 7b 5c 6d 61 67 6f | 6e 65 62 66 20 39 2e 32 |p.{\mago|nebf 9.2|
|00000860| 20 55 73 65 72 20 49 6d | 70 6c 65 6d 65 6e 74 61 | User Im|plementa|
|00000870| 74 69 6f 6e 73 7d 0a 0a | 49 6e 20 61 64 64 69 74 |tions}..|In addit|
|00000880| 69 6f 6e 20 74 6f 20 74 | 68 65 20 64 61 74 61 20 |ion to t|he data |
|00000890| 73 74 72 75 63 74 75 72 | 65 73 20 6c 69 73 74 65 |structur|es liste|
|000008a0| 64 20 69 6e 20 74 68 65 | 20 70 72 65 76 69 6f 75 |d in the| previou|
|000008b0| 73 20 73 65 63 74 69 6f | 6e 20 75 73 65 72 2d 64 |s sectio|n user-d|
|000008c0| 65 66 69 6e 65 64 20 0a | 64 61 74 61 20 73 74 72 |efined .|data str|
|000008d0| 75 63 74 75 72 65 73 20 | 63 61 6e 20 61 6c 73 6f |uctures |can also|
|000008e0| 20 62 65 20 75 73 65 64 | 20 61 73 20 61 63 74 75 | be used| as actu|
|000008f0| 61 6c 20 69 6d 70 6c 65 | 6d 65 6e 74 61 74 69 6f |al imple|mentatio|
|00000900| 6e 20 70 61 72 61 6d 65 | 74 65 72 73 20 70 72 6f |n parame|ters pro|
|00000910| 76 69 64 65 64 20 0a 74 | 68 65 79 20 66 75 6c 66 |vided .t|hey fulf|
|00000920| 69 6c 6c 20 63 65 72 74 | 61 69 6e 20 72 65 71 75 |ill cert|ain requ|
|00000930| 69 72 65 6d 65 6e 74 73 | 2e 0a 0a 5c 62 69 67 73 |irements|...\bigs|
|00000940| 6b 69 70 0a 7b 5c 62 66 | 20 39 2e 32 2e 31 20 44 |kip.{\bf| 9.2.1 D|
|00000950| 69 63 74 69 6f 6e 61 72 | 69 65 73 7d 0a 5c 73 6d |ictionar|ies}.\sm|
|00000960| 61 6c 6c 73 6b 69 70 0a | 41 6e 79 20 63 6c 61 73 |allskip.|Any clas|
|00000970| 73 20 24 64 69 63 5c 5f | 69 6d 70 6c 24 20 74 68 |s $dic\_|impl$ th|
|00000980| 61 74 20 70 72 6f 76 69 | 64 65 73 20 74 68 65 20 |at provi|des the |
|00000990| 66 6f 6c 6c 6f 77 69 6e | 67 20 6f 70 65 72 61 74 |followin|g operat|
|000009a0| 69 6f 6e 73 20 63 61 6e | 20 62 65 20 75 73 65 64 |ions can| be used|
|000009b0| 20 61 73 20 0a 61 63 74 | 75 61 6c 20 69 6d 70 6c | as .act|ual impl|
|000009c0| 65 6d 65 6e 74 61 74 69 | 6f 6e 20 70 61 72 61 6d |ementati|on param|
|000009d0| 65 74 65 72 20 66 6f 72 | 20 74 68 65 20 24 5c 5f |eter for| the $\_|
|000009e0| 64 69 63 74 69 6f 6e 61 | 72 79 5c 3c 4b 2c 49 2c |dictiona|ry\<K,I,|
|000009f0| 64 69 63 5c 5f 69 6d 70 | 6c 5c 3e 24 20 0a 61 6e |dic\_imp|l\>$ .an|
|00000a00| 64 20 74 68 65 20 24 5c | 5f 64 5c 5f 61 72 72 61 |d the $\|_d\_arra|
|00000a10| 79 5c 3c 49 2c 45 2c 64 | 69 63 5c 5f 69 6d 70 6c |y\<I,E,d|ic\_impl|
|00000a20| 5c 3e 24 20 64 61 74 61 | 20 74 79 70 65 73 20 28 |\>$ data| types (|
|00000a30| 63 66 2e 7e 73 65 63 74 | 69 6f 6e 73 7e 34 2e 33 |cf.~sect|ions~4.3|
|00000a40| 20 61 6e 64 20 34 2e 34 | 29 2e 0a 0a 5c 62 65 67 | and 4.4|)...\beg|
|00000a50| 69 6e 67 72 6f 75 70 0a | 5c 70 61 72 73 6b 69 70 |ingroup.|\parskip|
|00000a60| 20 30 70 74 5c 62 61 73 | 65 6c 69 6e 65 73 6b 69 | 0pt\bas|elineski|
|00000a70| 70 20 30 70 74 0a 5c 74 | 74 20 7b 5c 74 74 5c 6f |p 0pt.\t|t {\tt\o|
|00000a80| 62 65 79 73 70 61 63 65 | 73 5c 67 64 65 66 20 7b |beyspace|s\gdef {|
|00000a90| 5c 68 73 6b 69 70 2e 35 | 65 6d 7d 7d 20 5c 64 65 |\hskip.5|em}} \de|
|00000aa0| 66 5c 70 61 72 7b 5c 6c | 65 61 76 65 76 6d 6f 64 |f\par{\l|eavevmod|
|00000ab0| 65 5c 65 6e 64 67 72 61 | 66 7d 20 5c 63 61 74 63 |e\endgra|f} \catc|
|00000ac0| 6f 64 65 60 5c 60 3d 5c | 61 63 74 69 76 65 0a 5c |ode`\`=\|active.\|
|00000ad0| 6f 62 65 79 6c 69 6e 65 | 73 20 5c 74 74 76 65 72 |obeyline|s \ttver|
|00000ae0| 62 61 74 69 6d 0a 0a 74 | 79 70 65 64 65 66 20 2e |batim..t|ypedef .|
|00000af0| 2e 2e 20 64 69 63 5f 69 | 6d 70 6c 5f 69 74 65 6d |.. dic_i|mpl_item|
|00000b00| 3b 0a 0a 63 6c 61 73 73 | 20 64 69 63 5f 69 6d 70 |;..class| dic_imp|
|00000b10| 6c 20 7b 0a 0a 20 76 69 | 72 74 75 61 6c 20 69 6e |l {.. vi|rtual in|
|00000b20| 74 20 20 63 6d 70 28 47 | 65 6e 50 74 72 2c 20 47 |t  cmp(G|enPtr, G|
|00000b30| 65 6e 50 74 72 29 20 63 | 6f 6e 73 74 20 3d 20 30 |enPtr) c|onst = 0|
|00000b40| 3b 0a 20 76 69 72 74 75 | 61 6c 20 69 6e 74 20 20 |;. virtu|al int  |
|00000b50| 69 6e 74 5f 74 79 70 65 | 28 29 20 20 20 20 20 20 |int_type|()      |
|00000b60| 20 20 20 20 63 6f 6e 73 | 74 20 3d 20 30 3b 0a 20 |    cons|t = 0;. |
|00000b70| 76 69 72 74 75 61 6c 20 | 76 6f 69 64 20 63 6c 65 |virtual |void cle|
|00000b80| 61 72 5f 6b 65 79 28 47 | 65 6e 50 74 72 26 29 20 |ar_key(G|enPtr&) |
|00000b90| 20 63 6f 6e 73 74 20 3d | 20 30 3b 0a 20 76 69 72 | const =| 0;. vir|
|00000ba0| 74 75 61 6c 20 76 6f 69 | 64 20 63 6c 65 61 72 5f |tual voi|d clear_|
|00000bb0| 69 6e 66 28 47 65 6e 50 | 74 72 26 29 20 20 63 6f |inf(GenP|tr&)  co|
|00000bc0| 6e 73 74 20 3d 20 30 3b | 0a 20 76 69 72 74 75 61 |nst = 0;|. virtua|
|00000bd0| 6c 20 76 6f 69 64 20 63 | 6f 70 79 5f 6b 65 79 28 |l void c|opy_key(|
|00000be0| 47 65 6e 50 74 72 26 29 | 20 20 20 63 6f 6e 73 74 |GenPtr&)|   const|
|00000bf0| 20 3d 20 30 3b 0a 20 76 | 69 72 74 75 61 6c 20 76 | = 0;. v|irtual v|
|00000c00| 6f 69 64 20 63 6f 70 79 | 5f 69 6e 66 28 47 65 6e |oid copy|_inf(Gen|
|00000c10| 50 74 72 26 29 20 20 20 | 63 6f 6e 73 74 20 3d 20 |Ptr&)   |const = |
|00000c20| 30 3b 0a 0a 70 75 62 6c | 69 63 3a 0a 0a 20 64 69 |0;..publ|ic:.. di|
|00000c30| 63 5f 69 6d 70 6c 28 29 | 3b 0a 20 64 69 63 5f 69 |c_impl()|;. dic_i|
|00000c40| 6d 70 6c 28 63 6f 6e 73 | 74 20 64 69 63 5f 69 6d |mpl(cons|t dic_im|
|00000c50| 70 6c 26 29 3b 0a 20 76 | 69 72 74 75 61 6c 20 7e |pl&);. v|irtual ~|
|00000c60| 64 69 63 5f 69 6d 70 6c | 28 29 3b 0a 0a 20 64 69 |dic_impl|();.. di|
|00000c70| 63 5f 69 6d 70 6c 26 20 | 6f 70 65 72 61 74 6f 72 |c_impl& |operator|
|00000c80| 3d 28 63 6f 6e 73 74 20 | 64 69 63 5f 69 6d 70 6c |=(const |dic_impl|
|00000c90| 26 29 3b 0a 0a 20 47 65 | 6e 50 74 72 20 6b 65 79 |&);.. Ge|nPtr key|
|00000ca0| 28 64 69 63 5f 69 6d 70 | 6c 5f 69 74 65 6d 29 20 |(dic_imp|l_item) |
|00000cb0| 20 63 6f 6e 73 74 3b 0a | 20 47 65 6e 50 74 72 20 | const;.| GenPtr |
|00000cc0| 69 6e 66 28 64 69 63 5f | 69 6d 70 6c 5f 69 74 65 |inf(dic_|impl_ite|
|00000cd0| 6d 29 20 20 63 6f 6e 73 | 74 3b 0a 0a 20 64 69 63 |m)  cons|t;.. dic|
|00000ce0| 5f 69 6d 70 6c 5f 69 74 | 65 6d 20 69 6e 73 65 72 |_impl_it|em inser|
|00000cf0| 74 28 47 65 6e 50 74 72 | 2c 47 65 6e 50 74 72 29 |t(GenPtr|,GenPtr)|
|00000d00| 3b 0a 20 64 69 63 5f 69 | 6d 70 6c 5f 69 74 65 6d |;. dic_i|mpl_item|
|00000d10| 20 6c 6f 6f 6b 75 70 28 | 47 65 6e 50 74 72 29 20 | lookup(|GenPtr) |
|00000d20| 20 63 6f 6e 73 74 3b 0a | 20 64 69 63 5f 69 6d 70 | const;.| dic_imp|
|00000d30| 6c 5f 69 74 65 6d 20 66 | 69 72 73 74 5f 69 74 65 |l_item f|irst_ite|
|00000d40| 6d 28 29 20 20 20 20 63 | 6f 6e 73 74 3b 0a 20 64 |m()    c|onst;. d|
|00000d50| 69 63 5f 69 6d 70 6c 5f | 69 74 65 6d 20 6e 65 78 |ic_impl_|item nex|
|00000d60| 74 5f 69 74 65 6d 28 64 | 69 63 5f 69 6d 70 6c 5f |t_item(d|ic_impl_|
|00000d70| 69 74 65 6d 29 20 63 6f | 6e 73 74 3b 0a 0a 20 64 |item) co|nst;.. d|
|00000d80| 69 63 5f 69 6d 70 6c 5f | 69 74 65 6d 20 69 74 65 |ic_impl_|item ite|
|00000d90| 6d 28 76 6f 69 64 2a 20 | 70 29 20 63 6f 6e 73 74 |m(void* |p) const|
|00000da0| 20 7b 20 72 65 74 75 72 | 6e 20 64 69 63 5f 69 6d | { retur|n dic_im|
|00000db0| 70 6c 5f 69 74 65 6d 28 | 70 29 3b 20 7d 0a 0a 20 |pl_item(|p); }.. |
|00000dc0| 76 6f 69 64 20 20 20 20 | 63 68 61 6e 67 65 5f 69 |void    |change_i|
|00000dd0| 6e 66 28 64 69 63 5f 69 | 6d 70 6c 5f 69 74 65 6d |nf(dic_i|mpl_item|
|00000de0| 2c 47 65 6e 50 74 72 29 | 3b 0a 20 76 6f 69 64 20 |,GenPtr)|;. void |
|00000df0| 20 20 20 64 65 6c 5f 69 | 74 65 6d 28 64 69 63 5f |   del_i|tem(dic_|
|00000e00| 69 6d 70 6c 5f 69 74 65 | 6d 29 3b 0a 20 76 6f 69 |impl_ite|m);. voi|
|00000e10| 64 20 20 20 20 64 65 6c | 28 47 65 6e 50 74 72 29 |d    del|(GenPtr)|
|00000e20| 3b 0a 20 76 6f 69 64 20 | 20 20 20 63 6c 65 61 72 |;. void |   clear|
|00000e30| 28 29 3b 0a 0a 20 69 6e | 74 20 20 20 20 20 73 69 |();.. in|t     si|
|00000e40| 7a 65 28 29 20 63 6f 6e | 73 74 3b 0a 7d 3b 0a 0a |ze() con|st;.};..|
|00000e50| 5c 65 6e 64 67 72 6f 75 | 70 0a 0a 0a 5c 62 69 67 |\endgrou|p...\big|
|00000e60| 73 6b 69 70 0a 7b 5c 62 | 66 20 39 2e 32 2e 32 20 |skip.{\b|f 9.2.2 |
|00000e70| 50 72 69 6f 72 69 74 79 | 20 51 75 65 75 65 73 7d |Priority| Queues}|
|00000e80| 0a 5c 73 6d 61 6c 6c 73 | 6b 69 70 0a 41 6e 79 20 |.\smalls|kip.Any |
|00000e90| 63 6c 61 73 73 20 24 70 | 72 69 6f 5c 5f 69 6d 70 |class $p|rio\_imp|
|00000ea0| 6c 24 20 74 68 61 74 20 | 70 72 6f 76 69 64 65 73 |l$ that |provides|
|00000eb0| 20 74 68 65 20 66 6f 6c | 6c 6f 77 69 6e 67 20 6f | the fol|lowing o|
|00000ec0| 70 65 72 61 74 69 6f 6e | 73 20 63 61 6e 20 62 65 |peration|s can be|
|00000ed0| 20 75 73 65 64 20 61 73 | 20 0a 61 63 74 75 61 6c | used as| .actual|
|00000ee0| 20 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 20 | impleme|ntation |
|00000ef0| 70 61 72 61 6d 65 74 65 | 72 20 66 6f 72 20 74 68 |paramete|r for th|
|00000f00| 65 20 24 5c 5f 70 72 69 | 6f 72 69 74 79 5c 5f 71 |e $\_pri|ority\_q|
|00000f10| 75 65 75 65 5c 3c 4b 2c | 49 2c 70 72 69 6f 5c 5f |ueue\<K,|I,prio\_|
|00000f20| 69 6d 70 6c 5c 3e 24 0a | 64 61 74 61 20 74 79 70 |impl\>$.|data typ|
|00000f30| 65 20 28 63 66 2e 7e 73 | 65 63 74 69 6f 6e 7e 34 |e (cf.~s|ection~4|
|00000f40| 2e 31 29 2e 0a 0a 5c 62 | 65 67 69 6e 67 72 6f 75 |.1)...\b|egingrou|
|00000f50| 70 0a 5c 70 61 72 73 6b | 69 70 20 30 70 74 5c 62 |p.\parsk|ip 0pt\b|
|00000f60| 61 73 65 6c 69 6e 65 73 | 6b 69 70 20 30 70 74 0a |aselines|kip 0pt.|
|00000f70| 5c 74 74 20 7b 5c 74 74 | 5c 6f 62 65 79 73 70 61 |\tt {\tt|\obeyspa|
|00000f80| 63 65 73 5c 67 64 65 66 | 20 7b 5c 68 73 6b 69 70 |ces\gdef| {\hskip|
|00000f90| 2e 35 65 6d 7d 7d 20 5c | 64 65 66 5c 70 61 72 7b |.5em}} \|def\par{|
|00000fa0| 5c 6c 65 61 76 65 76 6d | 6f 64 65 5c 65 6e 64 67 |\leavevm|ode\endg|
|00000fb0| 72 61 66 7d 20 5c 63 61 | 74 63 6f 64 65 60 5c 60 |raf} \ca|tcode`\`|
|00000fc0| 3d 5c 61 63 74 69 76 65 | 0a 5c 6f 62 65 79 6c 69 |=\active|.\obeyli|
|00000fd0| 6e 65 73 20 5c 74 74 76 | 65 72 62 61 74 69 6d 0a |nes \ttv|erbatim.|
|00000fe0| 0a 74 79 70 65 64 65 66 | 20 2e 2e 2e 20 70 72 69 |.typedef| ... pri|
|00000ff0| 6f 5f 69 6d 70 6c 5f 69 | 74 65 6d 3b 0a 0a 63 6c |o_impl_i|tem;..cl|
|00001000| 61 73 73 20 70 72 69 6f | 5f 69 6d 70 6c 20 7b 20 |ass prio|_impl { |
|00001010| 0a 0a 20 76 69 72 74 75 | 61 6c 20 69 6e 74 20 20 |.. virtu|al int  |
|00001020| 63 6d 70 28 47 65 6e 50 | 74 72 2c 20 47 65 6e 50 |cmp(GenP|tr, GenP|
|00001030| 74 72 29 20 63 6f 6e 73 | 74 20 3d 20 30 3b 0a 20 |tr) cons|t = 0;. |
|00001040| 76 69 72 74 75 61 6c 20 | 69 6e 74 20 20 69 6e 74 |virtual |int  int|
|00001050| 5f 74 79 70 65 28 29 20 | 20 20 20 20 20 20 20 20 |_type() |        |
|00001060| 20 63 6f 6e 73 74 20 3d | 20 30 3b 0a 20 76 69 72 | const =| 0;. vir|
|00001070| 74 75 61 6c 20 76 6f 69 | 64 20 63 6c 65 61 72 5f |tual voi|d clear_|
|00001080| 6b 65 79 28 47 65 6e 50 | 74 72 26 29 20 20 63 6f |key(GenP|tr&)  co|
|00001090| 6e 73 74 20 3d 20 30 3b | 0a 20 76 69 72 74 75 61 |nst = 0;|. virtua|
|000010a0| 6c 20 76 6f 69 64 20 63 | 6c 65 61 72 5f 69 6e 66 |l void c|lear_inf|
|000010b0| 28 47 65 6e 50 74 72 26 | 29 20 20 63 6f 6e 73 74 |(GenPtr&|)  const|
|000010c0| 20 3d 20 30 3b 0a 20 76 | 69 72 74 75 61 6c 20 76 | = 0;. v|irtual v|
|000010d0| 6f 69 64 20 63 6f 70 79 | 5f 6b 65 79 28 47 65 6e |oid copy|_key(Gen|
|000010e0| 50 74 72 26 29 20 20 20 | 63 6f 6e 73 74 20 3d 20 |Ptr&)   |const = |
|000010f0| 30 3b 0a 20 76 69 72 74 | 75 61 6c 20 76 6f 69 64 |0;. virt|ual void|
|00001100| 20 63 6f 70 79 5f 69 6e | 66 28 47 65 6e 50 74 72 | copy_in|f(GenPtr|
|00001110| 26 29 20 20 20 63 6f 6e | 73 74 20 3d 20 30 3b 0a |&)   con|st = 0;.|
|00001120| 0a 70 75 62 6c 69 63 3a | 0a 0a 20 70 72 69 6f 5f |.public:|.. prio_|
|00001130| 69 6d 70 6c 28 29 3b 0a | 20 70 72 69 6f 5f 69 6d |impl();.| prio_im|
|00001140| 70 6c 28 69 6e 74 29 3b | 0a 20 70 72 69 6f 5f 69 |pl(int);|. prio_i|
|00001150| 6d 70 6c 28 69 6e 74 2c | 69 6e 74 29 3b 0a 20 70 |mpl(int,|int);. p|
|00001160| 72 69 6f 5f 69 6d 70 6c | 28 63 6f 6e 73 74 20 70 |rio_impl|(const p|
|00001170| 72 69 6f 5f 69 6d 70 6c | 26 29 3b 0a 20 76 69 72 |rio_impl|&);. vir|
|00001180| 74 75 61 6c 20 7e 70 72 | 69 6f 5f 69 6d 70 6c 28 |tual ~pr|io_impl(|
|00001190| 29 3b 0a 0a 20 70 72 69 | 6f 5f 69 6d 70 6c 26 20 |);.. pri|o_impl& |
|000011a0| 6f 70 65 72 61 74 6f 72 | 3d 28 63 6f 6e 73 74 20 |operator|=(const |
|000011b0| 70 72 69 6f 5f 69 6d 70 | 6c 26 29 3b 0a 0a 20 70 |prio_imp|l&);.. p|
|000011c0| 72 69 6f 5f 69 6d 70 6c | 5f 69 74 65 6d 20 69 6e |rio_impl|_item in|
|000011d0| 73 65 72 74 28 47 65 6e | 50 74 72 2c 47 65 6e 50 |sert(Gen|Ptr,GenP|
|000011e0| 74 72 29 3b 0a 20 70 72 | 69 6f 5f 69 6d 70 6c 5f |tr);. pr|io_impl_|
|000011f0| 69 74 65 6d 20 66 69 6e | 64 5f 6d 69 6e 28 29 20 |item fin|d_min() |
|00001200| 63 6f 6e 73 74 3b 0a 20 | 70 72 69 6f 5f 69 6d 70 |const;. |prio_imp|
|00001210| 6c 5f 69 74 65 6d 20 66 | 69 72 73 74 5f 69 74 65 |l_item f|irst_ite|
|00001220| 6d 28 29 20 63 6f 6e 73 | 74 3b 0a 20 70 72 69 6f |m() cons|t;. prio|
|00001230| 5f 69 6d 70 6c 5f 69 74 | 65 6d 20 6e 65 78 74 5f |_impl_it|em next_|
|00001240| 69 74 65 6d 28 70 72 69 | 6f 5f 69 6d 70 6c 5f 69 |item(pri|o_impl_i|
|00001250| 74 65 6d 29 20 63 6f 6e | 73 74 3b 0a 0a 20 70 72 |tem) con|st;.. pr|
|00001260| 69 6f 5f 69 6d 70 6c 5f | 69 74 65 6d 20 69 74 65 |io_impl_|item ite|
|00001270| 6d 28 76 6f 69 64 2a 20 | 70 29 20 63 6f 6e 73 74 |m(void* |p) const|
|00001280| 20 7b 20 72 65 74 75 72 | 6e 20 70 72 69 6f 5f 69 | { retur|n prio_i|
|00001290| 6d 70 6c 5f 69 74 65 6d | 28 70 29 3b 20 7d 0a 20 |mpl_item|(p); }. |
|000012a0| 0a 20 47 65 6e 50 74 72 | 20 6b 65 79 28 70 72 69 |. GenPtr| key(pri|
|000012b0| 6f 5f 69 6d 70 6c 5f 69 | 74 65 6d 29 20 63 6f 6e |o_impl_i|tem) con|
|000012c0| 73 74 3b 0a 20 47 65 6e | 50 74 72 20 69 6e 66 28 |st;. Gen|Ptr inf(|
|000012d0| 70 72 69 6f 5f 69 6d 70 | 6c 5f 69 74 65 6d 29 20 |prio_imp|l_item) |
|000012e0| 63 6f 6e 73 74 3b 0a 0a | 20 76 6f 69 64 20 64 65 |const;..| void de|
|000012f0| 6c 5f 6d 69 6e 28 29 3b | 0a 20 76 6f 69 64 20 64 |l_min();|. void d|
|00001300| 65 6c 5f 69 74 65 6d 28 | 70 72 69 6f 5f 69 6d 70 |el_item(|prio_imp|
|00001310| 6c 5f 69 74 65 6d 29 3b | 0a 20 76 6f 69 64 20 64 |l_item);|. void d|
|00001320| 65 63 72 65 61 73 65 5f | 6b 65 79 28 70 72 69 6f |ecrease_|key(prio|
|00001330| 5f 69 6d 70 6c 5f 69 74 | 65 6d 2c 47 65 6e 50 74 |_impl_it|em,GenPt|
|00001340| 72 29 3b 0a 20 76 6f 69 | 64 20 63 68 61 6e 67 65 |r);. voi|d change|
|00001350| 5f 69 6e 66 28 70 72 69 | 6f 5f 69 6d 70 6c 5f 69 |_inf(pri|o_impl_i|
|00001360| 74 65 6d 2c 47 65 6e 50 | 74 72 29 3b 0a 20 76 6f |tem,GenP|tr);. vo|
|00001370| 69 64 20 63 6c 65 61 72 | 28 29 3b 0a 20 20 0a 20 |id clear|();.  . |
|00001380| 69 6e 74 20 20 73 69 7a | 65 28 29 20 20 63 6f 6e |int  siz|e()  con|
|00001390| 73 74 3b 0a 7d 3b 0a 5c | 65 6e 64 67 72 6f 75 70 |st;.};.\|endgroup|
|000013a0| 0a 0a 5c 62 69 67 73 6b | 69 70 0a 7b 5c 62 66 20 |..\bigsk|ip.{\bf |
|000013b0| 39 2e 32 2e 33 20 53 6f | 72 74 65 64 20 53 65 71 |9.2.3 So|rted Seq|
|000013c0| 75 65 6e 63 65 73 7d 0a | 5c 73 6d 61 6c 6c 73 6b |uences}.|\smallsk|
|000013d0| 69 70 0a 41 6e 79 20 63 | 6c 61 73 73 20 24 73 65 |ip.Any c|lass $se|
|000013e0| 71 5c 5f 69 6d 70 6c 24 | 20 74 68 61 74 20 70 72 |q\_impl$| that pr|
|000013f0| 6f 76 69 64 65 73 20 74 | 68 65 20 66 6f 6c 6c 6f |ovides t|he follo|
|00001400| 77 69 6e 67 20 6f 70 65 | 72 61 74 69 6f 6e 73 20 |wing ope|rations |
|00001410| 63 61 6e 20 62 65 20 75 | 73 65 64 20 61 73 20 0a |can be u|sed as .|
|00001420| 61 63 74 75 61 6c 20 69 | 6d 70 6c 65 6d 65 6e 74 |actual i|mplement|
|00001430| 61 74 69 6f 6e 20 70 61 | 72 61 6d 65 74 65 72 20 |ation pa|rameter |
|00001440| 66 6f 72 20 74 68 65 20 | 24 5c 5f 73 6f 72 74 73 |for the |$\_sorts|
|00001450| 65 71 5c 3c 4b 2c 49 2c | 73 65 71 5c 5f 69 6d 70 |eq\<K,I,|seq\_imp|
|00001460| 6c 5c 3e 24 20 64 61 74 | 61 0a 74 79 70 65 20 28 |l\>$ dat|a.type (|
|00001470| 63 66 2e 7e 73 65 63 74 | 69 6f 6e 7e 34 2e 36 29 |cf.~sect|ion~4.6)|
|00001480| 2e 0a 0a 5c 62 65 67 69 | 6e 67 72 6f 75 70 0a 5c |...\begi|ngroup.\|
|00001490| 70 61 72 73 6b 69 70 20 | 30 70 74 5c 62 61 73 65 |parskip |0pt\base|
|000014a0| 6c 69 6e 65 73 6b 69 70 | 20 30 70 74 0a 5c 74 74 |lineskip| 0pt.\tt|
|000014b0| 20 7b 5c 74 74 5c 6f 62 | 65 79 73 70 61 63 65 73 | {\tt\ob|eyspaces|
|000014c0| 5c 67 64 65 66 20 7b 5c | 68 73 6b 69 70 2e 35 65 |\gdef {\|hskip.5e|
|000014d0| 6d 7d 7d 20 5c 64 65 66 | 5c 70 61 72 7b 5c 6c 65 |m}} \def|\par{\le|
|000014e0| 61 76 65 76 6d 6f 64 65 | 5c 65 6e 64 67 72 61 66 |avevmode|\endgraf|
|000014f0| 7d 20 5c 63 61 74 63 6f | 64 65 60 5c 60 3d 5c 61 |} \catco|de`\`=\a|
|00001500| 63 74 69 76 65 0a 5c 6f | 62 65 79 6c 69 6e 65 73 |ctive.\o|beylines|
|00001510| 20 5c 74 74 76 65 72 62 | 61 74 69 6d 0a 0a 74 79 | \ttverb|atim..ty|
|00001520| 70 65 64 65 66 20 2e 2e | 2e 20 73 65 71 5f 69 6d |pedef ..|. seq_im|
|00001530| 70 6c 5f 69 74 65 6d 3b | 0a 0a 63 6c 61 73 73 20 |pl_item;|..class |
|00001540| 73 65 71 5f 69 6d 70 6c | 20 20 7b 0a 0a 20 76 69 |seq_impl|  {.. vi|
|00001550| 72 74 75 61 6c 20 69 6e | 74 20 20 63 6d 70 28 47 |rtual in|t  cmp(G|
|00001560| 65 6e 50 74 72 2c 20 47 | 65 6e 50 74 72 29 20 63 |enPtr, G|enPtr) c|
|00001570| 6f 6e 73 74 20 3d 20 30 | 3b 0a 20 76 69 72 74 75 |onst = 0|;. virtu|
|00001580| 61 6c 20 69 6e 74 20 20 | 69 6e 74 5f 74 79 70 65 |al int  |int_type|
|00001590| 28 29 20 20 20 20 20 20 | 20 20 20 20 63 6f 6e 73 |()      |    cons|
|000015a0| 74 20 3d 20 30 3b 0a 20 | 76 69 72 74 75 61 6c 20 |t = 0;. |virtual |
|000015b0| 76 6f 69 64 20 63 6c 65 | 61 72 5f 6b 65 79 28 47 |void cle|ar_key(G|
|000015c0| 65 6e 50 74 72 26 29 20 | 20 63 6f 6e 73 74 20 3d |enPtr&) | const =|
|000015d0| 20 30 3b 0a 20 76 69 72 | 74 75 61 6c 20 76 6f 69 | 0;. vir|tual voi|
|000015e0| 64 20 63 6c 65 61 72 5f | 69 6e 66 28 47 65 6e 50 |d clear_|inf(GenP|
|000015f0| 74 72 26 29 20 20 63 6f | 6e 73 74 20 3d 20 30 3b |tr&)  co|nst = 0;|
|00001600| 0a 20 76 69 72 74 75 61 | 6c 20 76 6f 69 64 20 63 |. virtua|l void c|
|00001610| 6f 70 79 5f 6b 65 79 28 | 47 65 6e 50 74 72 26 29 |opy_key(|GenPtr&)|
|00001620| 20 20 20 63 6f 6e 73 74 | 20 3d 20 30 3b 0a 20 76 |   const| = 0;. v|
|00001630| 69 72 74 75 61 6c 20 76 | 6f 69 64 20 63 6f 70 79 |irtual v|oid copy|
|00001640| 5f 69 6e 66 28 47 65 6e | 50 74 72 26 29 20 20 20 |_inf(Gen|Ptr&)   |
|00001650| 63 6f 6e 73 74 20 3d 20 | 30 3b 0a 0a 70 75 62 6c |const = |0;..publ|
|00001660| 69 63 3a 0a 0a 20 73 65 | 71 5f 69 6d 70 6c 28 29 |ic:.. se|q_impl()|
|00001670| 3b 0a 20 73 65 71 5f 69 | 6d 70 6c 28 63 6f 6e 73 |;. seq_i|mpl(cons|
|00001680| 74 20 73 65 71 5f 69 6d | 70 6c 26 29 3b 0a 20 76 |t seq_im|pl&);. v|
|00001690| 69 72 74 75 61 6c 20 7e | 73 65 71 5f 69 6d 70 6c |irtual ~|seq_impl|
|000016a0| 28 29 3b 0a 0a 20 73 65 | 71 5f 69 6d 70 6c 26 20 |();.. se|q_impl& |
|000016b0| 6f 70 65 72 61 74 6f 72 | 3d 28 63 6f 6e 73 74 20 |operator|=(const |
|000016c0| 73 65 71 5f 69 6d 70 6c | 26 29 3b 0a 20 73 65 71 |seq_impl|&);. seq|
|000016d0| 5f 69 6d 70 6c 26 20 63 | 6f 6e 63 28 73 65 71 5f |_impl& c|onc(seq_|
|000016e0| 69 6d 70 6c 26 29 3b 0a | 20 0a 20 73 65 71 5f 69 |impl&);.| . seq_i|
|000016f0| 6d 70 6c 5f 69 74 65 6d | 20 69 6e 73 65 72 74 28 |mpl_item| insert(|
|00001700| 47 65 6e 50 74 72 2c 47 | 65 6e 50 74 72 29 3b 0a |GenPtr,G|enPtr);.|
|00001710| 20 73 65 71 5f 69 6d 70 | 6c 5f 69 74 65 6d 20 69 | seq_imp|l_item i|
|00001720| 6e 73 65 72 74 5f 61 74 | 5f 69 74 65 6d 28 73 65 |nsert_at|_item(se|
|00001730| 71 5f 69 6d 70 6c 5f 69 | 74 65 6d 2c 47 65 6e 50 |q_impl_i|tem,GenP|
|00001740| 74 72 2c 47 65 6e 50 74 | 72 29 3b 0a 20 73 65 71 |tr,GenPt|r);. seq|
|00001750| 5f 69 6d 70 6c 5f 69 74 | 65 6d 20 6c 6f 6f 6b 75 |_impl_it|em looku|
|00001760| 70 28 47 65 6e 50 74 72 | 29 20 20 20 20 20 20 63 |p(GenPtr|)      c|
|00001770| 6f 6e 73 74 3b 0a 20 73 | 65 71 5f 69 6d 70 6c 5f |onst;. s|eq_impl_|
|00001780| 69 74 65 6d 20 6c 6f 63 | 61 74 65 28 47 65 6e 50 |item loc|ate(GenP|
|00001790| 74 72 29 20 20 20 20 20 | 20 63 6f 6e 73 74 3b 0a |tr)     | const;.|
|000017a0| 20 73 65 71 5f 69 6d 70 | 6c 5f 69 74 65 6d 20 6c | seq_imp|l_item l|
|000017b0| 6f 63 61 74 65 5f 70 72 | 65 64 28 47 65 6e 50 74 |ocate_pr|ed(GenPt|
|000017c0| 72 29 20 63 6f 6e 73 74 | 3b 0a 20 73 65 71 5f 69 |r) const|;. seq_i|
|000017d0| 6d 70 6c 5f 69 74 65 6d | 20 73 75 63 63 28 73 65 |mpl_item| succ(se|
|000017e0| 71 5f 69 6d 70 6c 5f 69 | 74 65 6d 29 20 63 6f 6e |q_impl_i|tem) con|
|000017f0| 73 74 3b 0a 20 73 65 71 | 5f 69 6d 70 6c 5f 69 74 |st;. seq|_impl_it|
|00001800| 65 6d 20 70 72 65 64 28 | 73 65 71 5f 69 6d 70 6c |em pred(|seq_impl|
|00001810| 5f 69 74 65 6d 29 20 63 | 6f 6e 73 74 3b 0a 20 73 |_item) c|onst;. s|
|00001820| 65 71 5f 69 6d 70 6c 5f | 69 74 65 6d 20 69 74 65 |eq_impl_|item ite|
|00001830| 6d 28 76 6f 69 64 2a 20 | 70 29 20 63 6f 6e 73 74 |m(void* |p) const|
|00001840| 20 7b 20 72 65 74 75 72 | 6e 20 73 65 71 5f 69 6d | { retur|n seq_im|
|00001850| 70 6c 5f 69 74 65 6d 28 | 70 29 3b 20 7d 0a 20 0a |pl_item(|p); }. .|
|00001860| 20 47 65 6e 50 74 72 20 | 6b 65 79 28 73 65 71 5f | GenPtr |key(seq_|
|00001870| 69 6d 70 6c 5f 69 74 65 | 6d 29 20 63 6f 6e 73 74 |impl_ite|m) const|
|00001880| 3b 0a 20 47 65 6e 50 74 | 72 20 69 6e 66 28 73 65 |;. GenPt|r inf(se|
|00001890| 71 5f 69 6d 70 6c 5f 69 | 74 65 6d 29 20 63 6f 6e |q_impl_i|tem) con|
|000018a0| 73 74 3b 0a 20 0a 20 76 | 6f 69 64 20 64 65 6c 28 |st;. . v|oid del(|
|000018b0| 47 65 6e 50 74 72 29 3b | 20 0a 20 76 6f 69 64 20 |GenPtr);| . void |
|000018c0| 64 65 6c 5f 69 74 65 6d | 28 73 65 71 5f 69 6d 70 |del_item|(seq_imp|
|000018d0| 6c 5f 69 74 65 6d 29 3b | 20 0a 20 76 6f 69 64 20 |l_item);| . void |
|000018e0| 63 68 61 6e 67 65 5f 69 | 6e 66 28 73 65 71 5f 69 |change_i|nf(seq_i|
|000018f0| 6d 70 6c 5f 69 74 65 6d | 2c 47 65 6e 50 74 72 29 |mpl_item|,GenPtr)|
|00001900| 3b 0a 20 76 6f 69 64 20 | 73 70 6c 69 74 5f 61 74 |;. void |split_at|
|00001910| 5f 69 74 65 6d 28 73 65 | 71 5f 69 6d 70 6c 5f 69 |_item(se|q_impl_i|
|00001920| 74 65 6d 2c 73 65 71 5f | 69 6d 70 6c 26 2c 73 65 |tem,seq_|impl&,se|
|00001930| 71 5f 69 6d 70 6c 26 29 | 3b 0a 20 76 6f 69 64 20 |q_impl&)|;. void |
|00001940| 72 65 76 65 72 73 65 5f | 69 74 65 6d 73 28 73 65 |reverse_|items(se|
|00001950| 71 5f 69 6d 70 6c 5f 69 | 74 65 6d 2c 73 65 71 5f |q_impl_i|tem,seq_|
|00001960| 69 6d 70 6c 5f 69 74 65 | 6d 29 3b 20 0a 20 76 6f |impl_ite|m); . vo|
|00001970| 69 64 20 63 6c 65 61 72 | 28 29 3b 0a 20 0a 20 69 |id clear|();. . i|
|00001980| 6e 74 20 20 73 69 7a 65 | 28 29 20 20 63 6f 6e 73 |nt  size|()  cons|
|00001990| 74 3b 0a 7d 3b 0a 0a 5c | 65 6e 64 67 72 6f 75 70 |t;.};..\|endgroup|
|000019a0| 0a 0a 5c 76 66 69 6c 6c | 5c 65 6a 65 63 74 0a 0a |..\vfill|\eject..|
|000019b0| 5c 76 67 6c 75 65 20 31 | 30 63 6d 0a 5c 76 66 69 |\vglue 1|0cm.\vfi|
|000019c0| 6c 6c 5c 65 6a 65 63 74 | 0a                      |ll\eject|.       |
+--------+-------------------------+-------------------------+--------+--------+